package com.dyz.leetcode;

public class MinPathSum64 {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        if(n==0){return 0;}
        int m = grid[0].length;
        if(m==0){return 0;}

        int[][] dp = new int[n][m];

        //初始化
        dp[0][0] = grid[0][0];
        for(int i=1; i<n;i++){
            dp[i][0] = grid[i][0] +dp[i-1][0];
        }

        for(int j=1; j<m; j++){
            dp[0][j] = grid[0][j] +dp[0][j-1];
        }

        for(int x=1; x<n;x++){
            for(int y=1; y<m; y++){
                dp[x][y] = Math.min(dp[x-1][y], dp[x][y-1]) + grid[x][y];
            }
        }
        return dp[n-1][m-1];
    }
}
